package me.mingshan.leetcode;

/**
 * 删除链表的倒数第 N 个结点
 *
 * 给定一个链表，删除链表的倒数第n个结点，并且返回链表的头结点。
 *
 * 输入：head = [1,2,3,4,5], n = 2
 * 输出：[1,2,3,5]
 *
 */
public class L_19_RemoveNthFromEnd {

    public static void main(String[] args) {
        ListNode l1 = new ListNode(2);
        ListNode l12 = new ListNode(4);
        ListNode l13 = new ListNode(5);
        l1.next = l12;
        l12.next = l13;

        ListNode listNode = removeNthFromEnd2(l1, 2);
        ListNode.print(listNode);
    }


    /**
     *
     * 快慢指针
     *
     * 第一次遍历，统计链表的长度len
     * 第二次遍历，找到倒数第n个结点  index = len - n + 1
     *
     *
     * @param head
     * @param n
     * @return
     */
    public static ListNode removeNthFromEnd2(ListNode head, int n) {
        int len = 0;
        ListNode curr = head;
        while (curr != null) {
            len++;
            curr = curr.next;
        }

        int index = len - n + 1;
        curr = head;
        ListNode pre = null;

        int count = 0;

        while (curr != null) {
            count++;
            if (count == index) {
                if (pre == null) {
                    head = curr.next;
                } else {
                    pre.next = curr.next;
                }
            }

            pre = curr;
            curr = curr.next;
        }

        return head;
    }

    /**
     * 快慢指针,
     * 让快指针先走n步，然后快慢指针同时开始走，当快指针走到末尾时，慢指针指向的节点就是倒数第n个节点
     *
     * @param head
     * @param n
     * @return
     */
    public static ListNode removeNthFromEnd(ListNode head, int n) {
        if (head == null) {
            return null;
        }

        if (n <= 0) {
            return head;
        }

        int r = 0;
        ListNode fast = head;
        ListNode slow = null;
        ListNode prev = null;

        while (fast != null) {
            if (r >= n - 1) {
                if (slow == null) {
                    slow = head;
                }

                if (fast.next == null) {
                    break;
                }

                prev = slow;
                slow = slow.next;
            }

            r++;
            fast = fast.next;
        }

        if (slow != null) {
            if (slow == head) {
                ListNode next = head.next;
                if (next == null) {
                    return null;
                }

                head.next = null;
                head = next;
            } else {
                prev.next = slow.next;
                slow.next = null;
            }
        }

        return head;
    }

}
